package com.wc.算法基础课.D第四讲数学知识.矩阵乘法.斐波那契;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/4/4 23:57
 * @description https://www.acwing.com/activity/content/problem/content/9879/
 */
public class Main {
    static int[][] m = new int[][]{{0, 1}, {1, 1}};
    static int x;
    static int P = 10000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            x = sc.nextInt();
            if (x == -1) break;
            int[][] res = qkm(m, x);
            System.out.println(res[0][0]);
        }
    }

    static int[][] qkm(int[][] a, int b) {
        int[][] res = new int[][]{{0, 1}, {0, 0}};
        while (b > 0) {
            if ((b & 1) == 1) res = mulMatrix(res, a);
            a = mulMatrix(a, a);
            b >>= 1;
        }
        return res;
    }

    static int[][] mulMatrix(int[][] a, int[][] b) {
        int[][] res = new int[2][2];

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % P;
                }
            }
        }
        return res;
    }
}
